package com.sicheng.lc.lc笔试.京东篇;

import java.util.Arrays;
import java.util.Scanner;

public class 通信距离 {


    public static void main(String[] args) {
        // write your code here

        //时间限制： 3000MS
        //内存限制： 589824KB
        //题目描述：
        //       Alice和Bob需要采购会议场馆内的无线路由器。
        //       每一种路由器有一个参数k用于度量其通信距离。将场馆视为一个二维平面并将路由器视为该平面上的点，
        //       两台参数为k的路由器只能在他们所在位置的曼哈顿距离不超过k的前提下直接通信。
        //       两个点(x1,y1)和(x2,y2)之间的曼哈顿距离被定义为|x1-x2|+|y1-y2|
        //
        //       给出场馆内需要安装无线路由器的所有位置的坐标，请你计算出若他们只采购一种路由器，
        //       则其参数k至少需要为多少才能使得任意两个路由器之间都能够互相通信。
        //
        //       能够互相通信的定义如下：存在一个路由器序列v1,v2,…,vc，
        //       该序列中任意两个相邻路由器之间可以直接连接，则v1和vc之间可以互相通信。
        //输入描述
        //第一行有一个正整数n(1<=n<=1000)，代表需要安装路由器的位置数量。
        //
        //第二行有n个整数，第i个代表编号为i的位置的x坐标。
        //
        //第三行有n个整数，第i个代表编号为i的位置的y坐标。
        //
        //坐标的绝对值不超过1000000000。
        //
        //输出描述
        //输出一个正整数，代表能够使得任意两个路由器在允许中继的前提下能够互相通信的参数的最小值。
        /*
5
3 0 1 1 4
3 1 0 1 1
        */
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            nums[i][1] = scanner.nextInt();
        }

        System.out.println(prime(nums));


    }


    private static long prime(int[][] nums) {

        int n = nums.length;
        long[][] g = new long[n + 1][n + 1];
        boolean[] st = new boolean[n + 1];
        long[] dist = new long[n + 1];
        long res = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                g[i + 1][j + 1] = Math.abs(nums[i][0] - nums[j][0]) + Math.abs(nums[i][1] - nums[j][1]);
                g[j + 1][i + 1] = g[i + 1][j + 1];
            }
        }

        Arrays.fill(dist, Long.MAX_VALUE >> 3);
        dist[1] = 0;

        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            st[t] = true;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && g[j][t] < dist[j]) {
                    dist[j] = g[j][t];
                }
            }
            res = Math.max(res, dist[t]);
        }

        return res;
    }
}
